package Array;//字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
//
// 
//
// 示例： 
//
// 
//输入：S = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca", "defegde", "hijhklij"。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
// 
//
// 
//
// 提示： 
//
// 
// S的长度在[1, 500]之间。 
// S只包含小写字母 'a' 到 'z' 。 
// 
// Related Topics 贪心 哈希表 双指针 字符串 👍 706 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class partitionLabels {

    public static List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();

        //key为字符，value为int[]{start, end},为第一次出现的下标和最后一次出现的下标.
        HashMap<Character, int[]> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char key = s.charAt(i);
            if (!map.containsKey(key)){
                //如果当前不包含当前字符说明是第一次出现
                map.put(key,new int[]{i,0});
            }else{
                //map中存在，说明当前位置是再次出现的位置，一直更新
                int[] part = map.get(key);
                part[1] = i;
                map.put(key, part);
            }
        }
        //然后就是取出所有的数组进行区间合并。
        int[][] partitions = new int[map.size()][2];
        Set<Map.Entry<Character, int[]>> entries = map.entrySet();
        int i = 0;
        for (Map.Entry<Character, int[]> entry : entries) {
            partitions[i++] = entry.getValue();
        }
        Arrays.sort(partitions, ((o1, o2) -> o1[0]-o2[0]));

        //合并区间, partitions
        //几种情况, left和right是上一组
        int left = partitions[0][0];
        int right = partitions[0][1];
        for(int[] part: partitions){
            int li = part[0];
            int ri = part[1];
            if(right<li){
                //不重合
                res.add(right-left+1);
                left = li;
                right = ri;
            }else{
                //重合，进行合并
                left = Math.min(left,li);
                right = Math.max(right,ri);
            }
        }
        //最后添加
        res.add(right-left+1);

        return res;

    }
    public static List<Integer> partitionLabels1(String s) {
        List<Integer> res = new ArrayList<>();

        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0, end = 0;
        //map存每个字母最后出现的位置下标
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i),i);
        }
        //遍历一遍，取当前字符的最后下标和当前结束下标中最大的
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, map.get(s.charAt(i)));
            //如果当前位置等于结束的最大小标，直接截断保存
            if(i==end){
                res.add(end-start+1);
                start = i+1;
            }
        }
        return res;

    }

    public static void main(String[] args) {
        System.out.println(partitionLabels("ababcbacadefegdehijhklij"));
        System.out.println(partitionLabels1("ababcbacadefegdehijhklij"));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
